from typing import *
from heapq import heappop, heappush


class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        n, m = len(nums), len(queries)
        d = [0] * (n + 1)
        for l, r in queries:
            d[l] += 1
            d[r + 1] -= 1
        tot = 0
        for i, v in enumerate(nums):
            tot += d[i]
            if tot < v:
                return -1
        d = [0] * (n + 1)
        tot = 0
        queries.sort(key=lambda a: (a[0], -a[1]))
        ans, j = 0, 0
        q = []
        for i, v in enumerate(nums):
            tot += d[i]
            while tot < v and j < m and queries[j][0] <= i:
                if queries[j][1] >= i:
                    heappush(q, (-queries[j][1], queries[j][0]))
                j += 1
            while tot < v:
                r, l = heappop(q)
                tot += 1
                ans += 1
                d[-r + 1] -= 1
        return m - ans


s = Solution()

print(s.maxRemoval(nums=[1, 1, 1, 1], queries=[[1, 3], [0, 2], [1, 3], [1, 2]]))
print(s.maxRemoval(nums=[1, 2, 3, 4], queries=[[0, 3]]))
print(s.maxRemoval(nums=[2, 0, 2], queries=[[0, 2], [0, 2], [1, 1]]))
